home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / dflat8.zip / HTREE.C < prev    next >
Text File  |  1991-09-30  |  1KB  |  54 lines
  1. /* ------------------- htree.c -------------------- */
  2.  
  3. #include "dflat.h"
  4. #include "htree.h"
  5.  
  6. struct htree *ht;
  7. int root;
  8.  
  9. /* ------ build a Huffman tree from a frequency array ------ */
  10. void buildtree(void)
  11. {
  12.     int treect = 256;
  13.     int i;
  14.  
  15.     for (i = 0; i < treect; i++)    {
  16.         ht[i].parent = -1;
  17.         ht[i].right  = -1;
  18.         ht[i].left   = -1;
  19.     }
  20.     /* ---- build the huffman tree ----- */
  21.     while (1)   {
  22.         int h1 = -1, h2 = -1;
  23.         /* ---- find the two smallest frequencies ---- */
  24.         for (i = 0; i < treect; i++)   {
  25.             if (i != h1) {
  26.                 struct htree *htt = ht+i;
  27.                 if (htt->cnt > 0 && htt->parent == -1)   {
  28.                     if (h1 == -1 || htt->cnt < ht[h1].cnt) {
  29.                         if (h2 == -1 || ht[h1].cnt < ht[h2].cnt)
  30.                             h2 = h1;
  31.                         h1 = i;
  32.                     }
  33.                     else if (h2 == -1 || htt->cnt < ht[h2].cnt)
  34.                         h2 = i;
  35.                 }
  36.             }
  37.         }
  38.         if (h2 == -1) {
  39.             root = h1;
  40.             break;
  41.         }
  42.         /* --- combine two nodes and add one --- */
  43.         ht[h1].parent = treect;
  44.         ht[h2].parent = treect;
  45.         ht = realloc(ht, (treect+1) * sizeof(struct htree));
  46.         ht[treect].cnt = ht[h1].cnt + ht[h2].cnt;
  47.         ht[treect].right = h1;
  48.         ht[treect].left = h2;
  49.         ht[treect].parent = -1;
  50.         treect++;
  51.     }
  52. }
  53.  
  54.